package com.lijing.insertValueSearch;

public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i+1;
        }
        System.out.println(insertValueSearch(arr,0,arr.length-1,1111));
    }

    /**
     * 插值算法
     * @param arr 数组
     * @param left 左索引
     * @param right 右索引
     * @param finaVal 查找值
     * @return 返回findVal的索引，找到返回对应的下标，没找到返回-1
     */
    public static int insertValueSearch(int[] arr, int left, int right, int finaVal){
        System.out.println("cnt 1...");
        if(left > right || finaVal < arr[0] || finaVal > arr[arr.length-1]){
            return -1;
        }
        int mid = left + (right - left)*(finaVal - arr[left])/(arr[right] - arr[left]);
        int midVal = arr[mid];
        if(finaVal > midVal){
            //向右递归查找
            return insertValueSearch(arr, mid+1,right,finaVal);
        }else if(finaVal < midVal){
            //向左递归查找
            return insertValueSearch(arr, left, mid-1, finaVal);
        }else {
            return mid;
        }
    }
}
